package 统计满足K约束的子字符串数量II3261;

public class Solution {
    public long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
        long[][] arr = new long[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            int[] sign = new int[2];
            for (int j = i; j < s.length(); j++) {
                if(s.charAt(j) == '0'){
                    sign[0]++;
                }else {
                    sign[1]++;
                }
                if (sign[0] <= k || sign[1] <= k) {
                    arr[i][j] = 1;
                }
            }
        }
//        for (int i = 0; i < arr.length; ++i) {
//            for (int j = 0; j < arr[i].length; ++j) {
//                System.out.print(arr[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println("*");
        long[][] front = new long[s.length() + 1][s.length() + 1];
        for (int i = 0; i < front.length; i++) {
            for (int j = 0; j < front.length; j++) {
                if(i == 0 || j == 0){
                    front[i][j] = 0;
                }else {
                    front[i][j] = arr[i - 1][j - 1] + front[i - 1][j] + front[i][j - 1] - front[i - 1][j - 1];
                }
            }
        }
//        for (int i = 0; i < front.length; i++) {
//            for (int j = 0; j < front[i].length; j++) {
//                System.out.print(front[i][j] + " ");
//            }
//            System.out.println();
//        }
        long[] ans = new long[queries.length];
        for (int i = 0; i < queries.length; i++) {
            ans[i] = front[queries[i][1] + 1][queries[i][1] + 1] - front[queries[i][1] + 1][queries[i][0]] - front[queries[i][0]][queries[i][1] + 1] + front[queries[i][0]][queries[i][0]];
        }
        return ans;
    }
}
